package com.sunny.k_merge;

import java.util.ArrayList;
import java.util.Arrays;

// 利用胜者树来实现
public class KMerge3 {

    public static void main(String[] args) {

        KMerge1 kMerge1 = new KMerge1();
        ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(1,3,5,7,8,9));
        ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(1,2,3,5,6,10,11));
        ArrayList<Integer> list3 = new ArrayList<>(Arrays.asList(1,1,3,3,8,8,9,10));
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        lists.add(list1);
        lists.add(list2);
        lists.add(list3);
        ArrayList<Integer> res = kMerge1.sort(lists);
        res.forEach(System.out::println);

    }

    public ArrayList<Integer> sort(ArrayList<ArrayList<Integer>> arr){
        ArrayList<Integer> res = new ArrayList<>();
        int[] ind = new int[arr.size()];
        int n = 0;
        for(int i=0;i<arr.size();i++)
            n += arr.get(i).size();
        //建树
        int len = 1;
        while (len < arr.size()){
            len <<= 1;
        }
        TreeNode[] tree = new TreeNode[(len<<1)];
        for(int i=len;i<tree.length;i++){
            if(i-len < arr.size()){
                tree[i] = new TreeNode(arr.get(i-len).get(ind[i-len]), i-len);
                ind[i-len]++;
            }else{
                tree[i] = new TreeNode(Integer.MAX_VALUE, -1);
            }
        }
        for(int i=len-1;i>=1;i--){
            if(tree[2*i].data <= tree[2*i+1].data){
                tree[i] = new TreeNode(tree[2*i].data, tree[2*i].ind);
            }else{
                tree[i] = new TreeNode(tree[2*i+1].data, tree[2*i+1].ind);
            }
        }
        //取数
        int cnt = 0;
        while (cnt<n){
            res.add(tree[1].data);
            int tmpInd = tree[1].ind + len;
            ind[tree[1].ind]++;
            tree[tmpInd] = new TreeNode(arr.get(tree[1].ind).get(ind[tree[1].ind]),tree[1].ind);
            int find = tmpInd>>1;
            while (find >= 1){
                if(tree[2*find].data <= tree[2*find+1].data){
                    tree[find] = new TreeNode(tree[2*find].data, tree[2*find].ind);
                }else{
                    tree[find] = new TreeNode(tree[2*find+1].data, tree[2*find+1].ind);
                }
                find >>= 1;
            }
        }
        return res;
    }

}

class TreeNode{
    int data;
    int ind;

    public TreeNode(int data, int ind) {
        this.data = data;
        this.ind = ind;
    }
}